<?php
// https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/

// 如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为 lcs 是最长公共子序列嘛

//用两个指针 i 和 j 从后往前遍历 s1 和 s2，如果 s1[i]==s2[j]，那么这个字符一定在 lcs 中；
//否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个。

Class Solution
{
    public function longestCommonSubsequence($str1, $str2)
    {
        $str1_len = strlen($str1);
        $str2_len = strlen($str2);

        $dp = array();
        for($i=0; $i<=$str1_len; $i++) {
            for($j=0; $j<=$str2_len; $j++) {
                $dp[$i][$j] = 0;
            }
        }

        for ($k=1; $k<=$str1_len; $k++) {
            for ($l=1; $l<=$str2_len; $l++) {
                // 这里索引从1开始的 所以要-1
                if ($str1[$k-1] == $str2[$l-1]) {
                    $dp[$k][$l] = $dp[$k-1][$l-1] + 1;
                } else {
                    $dp[$k][$l] = max($dp[$k-1][$l], $dp[$k][$l-1]);
                }
            }
        }

        return $dp[$str1_len][$str2_len];
    }
}